package com.wyw.leetcode.learning.simple;


/**
 * leetcode topic 617
 * 合并二叉树
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/11/30 9:37
 */
public class Topic617 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;



        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);
        TreeNode node14 = new TreeNode(14);
        TreeNode node15 = new TreeNode(15);

        node6.left=node7;
        node6.right=node8;
        node7.left=node9;
        node9.left=node10;
        node9.right=node11;
        node10.left=node12;
        node8.left=node13;
        node8.right=node14;
        node13.left=node15;

        TreeNode treeNode = mergeTrees(node, node6);
        System.out.println("end");

    }

    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        }
        // 先合并根节点
        TreeNode root = new TreeNode((root1 == null ? 0 : root1.val) + (root2 == null ? 0 : root2.val));
        // 再递归合并左右子树
        root.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
        root.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
        return root;
    }

}

class TreeNode {
     int val;
     TreeNode left;
    TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
         this.right = right;
 }
 }
